题目分析

来一个简单题，看看小伙伴们能优化到什么程度？能否使用线性复杂度做出来这个题目呢？

模拟

数据量较小，我们使用模拟方法也可以求解。即建立一个大小为n x m的矩阵，然后遍历indices数组，每次修改n行和m列即可，最后判断矩阵中有多少个奇数。

算法的**时间复杂度为$O(max(mn, k \times max(m, n)))$，空间复杂度为$O(mn)$**，其中n，m是矩阵的行和列，k是索引数组indices的长度。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int>> array(n, vector<int>(m));
        int res = 0;
        for (auto v : indices) {
            for (int j = 0; j < m; j++) { array[v[0]][j]++; }
            for (int i = 0; i < n; i++) { array[i][v[1]]++; }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) { res += array[i][j] & 1; }
        }
        return res;
    }
};

优化模拟

要判断一个数是奇数还是偶数，我们只用关系它所在的行和列改变了多少次。因此我们使用两个一维矩阵表示所在的行改变了奇数次还是偶数次。false代表改变了偶数次，true代表改变了奇数次。

因此我们模拟时不用改变具体的每一个数，而是改变一行或者一列即可。最后计算第i行第j列是否为奇数时，只用关心对应的行和列是否不相等，如果行和列相等，那么说明它们改变了相同的次数，那么一定是偶数，否则一定是奇数。

算法的**时间复杂度为$O(mn)$，空间复杂度为$O(m + n)$**，其中n，m是矩阵的行和列。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<bool> row(n, false), col(m, false);
        int res = 0;
        for (auto v : indices) {
            row[v[0]] = !row[v[0]];
            col[v[1]] = !col[v[1]];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res += row[i] ^ col[j];
            }
        }
        return res;
    }
};

数学优化

数学优化就更加巧妙了，我们不关心每一个数是否为奇数还是偶数，只关心该行或者列是否为奇数还是偶数。有的小伙伴好奇，这不是和上面的算法一样吗？

但是上面的算法虽然在模拟时没有考虑每一个元素，但是在最后判断时仍然遍历了所有的元素。我们可以通过数学的方法节省遍历时的时间复杂度。

思考：如果某一行修改了奇数次，那么该行所有元素为奇数的个数为多少？是不是修改了偶数列的次数。对于每一个修改了奇数次的行都是这样。因此对于所有奇数行来说，元素为奇数的个数为：修改奇数次的行数量 x 修改偶数次的列数量。同理，对于所有偶数行来说，元素为奇数的个数为：修改偶数次的行数量 x 修改奇数次的列数量。

因此我们只要在优化模拟方法中，直接统计修改奇数次的行数量，和修改奇数次的列数量即可。修改偶数次的行数量 = n - 修改奇数次的行数量，列数量同理。

算法的**时间复杂度为$O(max(m, n, k))$，空间复杂度为$O(m + n)$**，其中n，m是矩阵的行和列，k是索引数组indices的长度。。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<bool> row(n, false), col(m, false);
        int rowOdd = 0, colOdd = 0, res = 0;
        for (auto v : indices) {
            row[v[0]] = !row[v[0]];
            col[v[1]] = !col[v[1]];
        }
        for (int i = 0; i < n; i++) {
            rowOdd += row[i];
        }
        for (int j = 0; j < m; j++) {
            colOdd += col[j];
        }
        return rowOdd * (m - colOdd) + colOdd * (n - rowOdd);
    }
};

刷题总结

数学技巧在某些场合下能够大大提高我们的算法复杂度，但是有些数学技巧难以想到，因此我们多做题的目的就是开拓自己的视野，以后遇到相似问题可以有所启发。这个题目重点掌握第二个方法，对于修改一行或者一列的问题很有帮助。做这类问题很少进行完全的模拟，都需要用到一些小技巧。但是像第三个数学优化，有的问题可能没有这个方法，但是第二个方法基本上都可以用得到。